package binaryTree;

//递归三部曲
//      1,  确定递归函数的参数和返回值
//        因为我们要比较的是根节点的两个子树是否是相互翻转的，
//        进而判断这个树是不是对称树，所以要比较的是两个树，
//        参数自然也是左子树节点和右子树节点。
//
//        返回值自然是bool类型。

//     2,   确定终止条件
//        要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！
//        否则后面比较数值的时候就会操作空指针了。

//节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）
//
//        左节点为空，右节点不为空，不对称，return false
//        左不为空，右为空，不对称 return false
//        左右都为空，对称，返回true
//        此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：
//
//        左右都不为空，比较节点数值，不相同就return false
//        此时左右节点不为空，且数值也不相同的情况我们也处理了。


//3,确定单层递归的逻辑
//        此时才进入单层递归的逻辑，单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况。
//
//        比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
//        比较内测是否对称，传入左节点的右孩子，右节点的左孩子。
//        如果左右都对称就返回true ，有一侧不对称就返回false


import java.util.Deque;
import java.util.LinkedList;
import java.util.Optional;
import java.util.Queue;

public class IsSymmetricTree {

    public boolean isSymmetric(TreeNode root) {
        if (root==null){
            return  true;
        }
        return  compare(root.left,root.right);

    }
    public  boolean compare(TreeNode left, TreeNode right){
        if (left==null&&right!=null||left!=null&&right==null){
            return  false;
        }
        if (left==null&&right==null){
            return  true;    //此时已经不需要继续向下递归了 直接返回
        }

        if (left.val!=right.val){  //为什么不将这个条件判断放在上面第一个条件中
                                  // 因为要确定left和right不为null的时候才可以进行left和right数值的判断
                                  //此时经过了两层 判断为空的操作走到这里已经去欸的那个left和right不为nullle
            return false;
        }
//上面都是递归停止的条件
//        if (left.val==right.val){     此时已经不需要再添加条件判断了  因为此时一定是左右的数值相等了
            return  compare(left.left,right.right)&&compare(right.left,left.right);
    }

//    这道题目的本质是要比较两个树（这两个树是根节点的左右子树），
//    遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。

    /**
     * 迭代法
     * 使用双端队列，相当于两个栈
     */
    public boolean isSymmetric2(TreeNode root) {
        if (root==null){
            return  true;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offerFirst(root.left);
        deque.offerLast(root.right);
        while (!deque.isEmpty()) {
            TreeNode leftNode = deque.pollFirst();
            TreeNode rightNode = deque.pollLast();
            if (leftNode == null && rightNode == null) {
                continue;
            }
//            if (leftNode == null && rightNode != null) {
//                return false;
//            }
//            if (leftNode != null && rightNode == null) {
//                return false;
//            }
//            if (leftNode.val != rightNode.val) {
//                return false;
//            }
            // 以上三个判断条件合并
            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
                return false;
            }
            Optional.ofNullable( deque.offerFirst(leftNode.left));
            Optional.ofNullable(deque.offerFirst(leftNode.right));
            Optional.ofNullable(deque.offerLast(rightNode.right));
            Optional.ofNullable(deque.offerLast(rightNode.left));
        }
        return true;
    }

    /**
     * 迭代法
     * 使用普通队列
     */
    public boolean isSymmetric3(TreeNode root) {
        Queue<TreeNode> deque = new LinkedList<>();
        deque.offer(root.left);
        deque.offer(root.right);
        while (!deque.isEmpty()) {
            TreeNode leftNode = deque.poll();
            TreeNode rightNode = deque.poll();
            if (leftNode == null && rightNode == null) {
                continue;
            }
//            if (leftNode == null && rightNode != null) {
//                return false;
//            }
//            if (leftNode != null && rightNode == null) {
//                return false;
//            }
//            if (leftNode.val != rightNode.val) {
//                return false;
//            }
            // 以上三个判断条件合并
            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
                return false;
            }
            // 这里顺序与使用Deque不同
            deque.offer(leftNode.left);
            deque.offer(rightNode.right);
            deque.offer(leftNode.right);
            deque.offer(rightNode.left);
        }
        return true;
    }




    public static void main(String[] args) {
        TreeNode root= new TreeNode(5);
        TreeNode treeNode1 = new TreeNode(3);
        TreeNode treeNode2=new TreeNode(3);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4= new TreeNode(3);
        root.left=treeNode1;
        root.right=treeNode3;
        treeNode1.left=treeNode2;
        treeNode3.right=treeNode4;

        IsSymmetricTree isSymmetricTree = new IsSymmetricTree();
        System.out.println(isSymmetricTree.isSymmetric(root));

    }

}
